package Link;

import java.util.List;

public class leet_148 {
    public static void main(String[] args) {
        ListNode pre = new ListNode(4);
        ListNode pre1 = new ListNode(2);
        ListNode pre2 = new ListNode(1);
        ListNode pre3 = new ListNode(3);

        pre.next = pre1;
        pre1.next = pre2;
        pre2.next = pre3;

        Solution_148 p =new Solution_148();
        p.sortList(pre);

    }
}


class Solution_148 {

    /**
     * 利用归并算法
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        return sort(head, null);
    }

    /**
     * 对2个node进行排序归并排序 其中left 代表起始点 right代表结束点
     * @return
     */
    public ListNode sort(ListNode left, ListNode right){
        if(left==right){return left;}

        // 前进找中间位置  一想到找中间位置就可以思考 快慢指针法
        ListNode fastNode = left;
        ListNode slowNode = left;

        while(fastNode.next!=null && fastNode.next.next!=null){
            fastNode=fastNode.next.next;
            slowNode = slowNode.next;
        }

        // 先排序右边 因为左边一旦置空就无法遍历了
        ListNode head2 = sort(slowNode.next, right);
        slowNode.next = null;
        ListNode head1 = sort(left, slowNode);

        return merge(head1, head2);
    }

    /**
     * 将2个Node合并
     */
    public ListNode merge(ListNode list1, ListNode list2){
        if(list1==null){
            return list2;
        }else if(list2==null) {
            return list1;
        }

        // 递归合并
        if(list1.val < list2.val){
            // 如果 list1小于list2 那么list1放在前面  在让list1.next与 list2比较
            list1.next = merge(list1.next, list2);
            return list1;
        }else {
            list2.next = merge(list1, list2.next);
            return list2;
        }

    }






    /**
     * 重构法   时间复杂度高
     * @param head
     * @return
     */
    public ListNode func1(ListNode head){
        if(head==null){return head;}
        // 构建一个节点
        ListNode curr =new ListNode(Integer.MIN_VALUE);
        curr.next = head;
        head = head.next;
        curr.next.next = null;

        // 结点为空
        while (head!=null){
            // 是否加入Node中
            boolean flag = false;
            // 遍历curr结点来找到 当前节点应该存放的位置
            ListNode pre = curr;
            ListNode next = pre.next;

            while(next!=null){
                // 找到一个位置
                // next.val > head.val 说明此时  pre.val <= head.val < next.val
                if(next.val > head.val){
                    flag = true;
                    pre.next = head;
                    ListNode tmp = head.next;
                    head.next = next;
                    head = tmp;
                    break;
                }
                pre = pre.next;
                next = next.next;
            }
            if(!flag){
                // 如果遍历玩都没有找到直接加在尾部
                pre.next = head;
                head = head.next;
                pre.next.next = null;
            }
        }
        return curr.next;
    }



}

